import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PolandNotation {
    public static void main(String[] args) {
//        //后缀表达式
//        //中缀表达式为：(12+4)*5-6
//        String suffixExpression = "12 4 + 5 * 6 -";
//        List<String> rpnList = getListString(suffixExpression);
//        System.out.println("rpnList = " + rpnList);
//        int result = calculate(rpnList);
//        System.out.println("结果为：" + result);

        //中缀表达式
        String infixExpression = "1+((2+3)*4)-5";
        List<String> infixExpressionList = toInfixExpressionList(infixExpression);
        System.out.println("中缀表达式对应的List = " + infixExpressionList);
        List<String> parseSuffixExpressionList = parseSuffixExpression(infixExpressionList);
        System.out.println("后缀表达式对应的List = " + parseSuffixExpressionList);
    }

    /**
     * 将中缀表达式转化为数组形式
     * @param s: 输入的中缀表达式
     * @return
     */
    public static List<String> toInfixExpressionList(String s){
        List<String> ls = new ArrayList<String>();
        int i = 0;
        String str;
        char c = ' ';
        do{
            if((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57){
                //注意这里需要将char类型转化为String类型
                ls.add("" + c);
                i++;
            }else{
                str = "";
                //注意这里 i < s.length() 放在最前面
                while(i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57){
                    //拼接多位数
                    str += c;
                    i++;
                }
                ls.add(str);
            }
        }while(i < s.length());
        return ls;
    }


    /**
     * 以空格分割，将后缀表达式转化为数组形式
     * @param suffixExpression:输入的后缀表达式
     * @return：返回以数组形式表示的后缀表达式
     */
    public static List<String> getListString(String suffixExpression){
        //以数组形式分割
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<>();
        //增强循环
        for(String ele : split){
            list.add(ele);
        }
        return list;
    }

    /**
     * 计算数组中后缀表达式的计算结果
     * @param ls：输入的后缀表达式
     * @return: 返回最后的结果
     */
    public static int calculate(List<String> ls){
        Stack<String> stack = new Stack<String>();
        for(String item : ls){
            //判断是否为多位数的正则表达式
            if(item.matches("\\d+")){
                stack.push(item);
            }else{
                int result = 0;
                //注意stack.pop()为String，要转为int
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                if(item.equals("+")){
                    result = num1 + num2;
                }else if(item.equals("-")){
                    result = num1 - num2;
                }else if(item.equals("*")){
                    result = num1 * num2;
                }else if(item.equals("/")){
                    result = num1 / num2;
                }else{
                    throw new RuntimeException();
                }
                //int型转换为String
                stack.push("" + result);
            }
        }
        return Integer.parseInt(stack.pop());
    }

    /**
     * 中缀转后缀
     * @param ls 输入的列表
     * @return 返回s2
     */
    public static List<String> parseSuffixExpression(List<String> ls){
        //存储符号栈
        Stack<String> s1 = new Stack<String>();
        //存储中间件
        List<String> s2 = new ArrayList<String>();
        for(String item : ls){
            if(item.matches("\\d+")){ //判断是否为数字
                s2.add(item);
            }else if(item.equals("(")){
                //当遇到“（”时，将“（”直接压入s1中
                s1.push(item);
            }else if(item.equals(")")){
                //当遇到“）”时，将s1中的“（”与“）”之间的元素加入到s2
                while(!s1.peek().equals("(")){
                    s2.add(s1.pop());
                }
                s1.pop();
            }else{
                //比较符号的优先级，若item优先级小于等于s1栈顶符号的优先级时，
                //将s1栈顶符号加入到s2中
                while(s1.size() != 0 && Operation.getValue(item) <= Operation.getValue(s1.peek())){
                    s2.add(s1.pop());
                }
                //将item压入s1中
                s1.push(item);
            }
        }
        //最后将s1栈中剩余的符号，加入到s2中
        while(s1.size() != 0){
            s2.add(s1.pop());
        }
        return s2;
    }
}

/**
 * 优先级比较类
 */
class Operation{
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;

    public static int getValue(String s){
        int result = 0;
        switch (s){
            case "+" : result = ADD; break;
            case "-" : result = SUB; break;
            case "*" : result = MUL; break;
            case "/" : result = DIV; break;
            default:
                System.out.println("不存在");
        }
        return result;
    }
}